package common.queue;

/**
 * Title: Dequeue
 * Author: Xutong Fan
 * Description: implement and array-based deque.
 */
@SuppressWarnings("unchecked")
public class Deque<Item> {
    private Item[] deque;
    private int size;
    private int headNext;
    private int tailNext;

    private int accessCount = 0;

    /***
     *constructor: create an empty Deque with initial
     *capacity of 10
     */
    public Deque() {
        this(10);
    }

    /***
     *constructor: create an empty Deque with initial
     *capacity of n
     */
    public Deque(int n) {
        deque = (Item[]) new Object[n];
        size = 0;
        headNext = 0;
        tailNext = 1;
    }

    /***
     *add an item to the front of the Deque
     *double the array capacity if Deque is full
     */
    public void addToFront(Item item) {
        if (size == deque.length) {
            resize(size * 2);
        }

        deque[headNext] = item;
        headNext = (headNext - 1 + deque.length) % deque.length;
        size++;
        accessCount++;
    }

    /***
     *add an item to the back of the Deque;
     *double the array capacity if the Deque is full
     ***/
    public void addToBack(Item item) {
        if (size == deque.length) {
            resize(size * 2);
        }
        deque[tailNext] = item;
        tailNext = (tailNext + 1 + deque.length) % deque.length;
        size++;
        accessCount++;
    }

    /***
     *remove and return the front item from the Deque;
     *throw EmptyDequeException if the Deque is empty;
     *reduce the array capacity by half if the size 
     *of the Deque size falls below floor(N/4) where
     *N is the array capacity, but do not resize it 
     *to be below the default capacity, which is 10
     ***/
    public Item getFirst() throws EmptyDequeException {
        if (isEmpty()) {
            throw new EmptyDequeException();
        }

        if (deque.length > 10 && size < Math.floor(deque.length * 1.0D / 4)) {
            resize(deque.length / 2);
        }

        int headIndex = (headNext + 1) % deque.length;
        Item first = deque[headIndex];
        accessCount++;

        deque[headIndex] = null;
        accessCount++;
        size--;
        headNext = headIndex;
        return first;
    }

    /***
     *remove and return the back item from the Deque;
     *throw EmptyDequeException if the Deque is empty;
     *reduce the array capacity by half if the size 
     *of the Deque size falls below floor(N/4) where
     *N is the array capacity, but do not resize it 
     *to be below the default capacity, which is 10
     ***/
    public Item getLast() throws EmptyDequeException {
        if (isEmpty()) {
            throw new EmptyDequeException();
        }

        if (deque.length > 10 && size < Math.floor(deque.length * 1.0D / 4)) {
            resize(deque.length / 2);
        }

        int tailIndex = (tailNext - 1 + deque.length) % deque.length;
        Item last = deque[tailIndex];
        accessCount++;

        deque[tailIndex] = null;
        accessCount++;
        size--;
        tailNext = tailIndex;

        return last;
    }

    /***
     *return true if the Deque is empty;
     *return false if the Deque is not empty
     ***/
    public boolean isEmpty() {
        return size == 0;
    }

    /***
     *return the size of the Deque (i.e. the 
     *number of elements currently in the Deque)
     ***/
    public int size() {
        return size;
    }

    /***
     *return but do not remove the front item in the Deque;
     *throw an EmptyDequeException if the Deque is empty
     */
    public Item peekFirst() throws EmptyDequeException {
        if (isEmpty()) {
            throw new EmptyDequeException();
        }

        int headIndex = (headNext + 1) % deque.length;
        accessCount++;
        return deque[headIndex];
    }

    /***
     *return but do not remove the back item in the Deque;
     *throw an EmptyDequeException if the Deque is empty
     */
    public Item peekLast() throws EmptyDequeException {
        if (isEmpty()) {
            throw new EmptyDequeException();
        }
        int tailIndex = (tailNext - 1 + deque.length) % deque.length;
        accessCount++;
        return deque[tailIndex];
    }

    /***
     *return the underlying array
     ***/
    public Item[] getArray() {
        Item[] array = (Item[]) new Object[size];
        int headIndex = headNext + 1;
        for (int i = 0; i < size; i++) {
            int index = (headIndex + i) % deque.length;
            array[i] = deque[index];
            accessCount++;
        }
        return array;
    }

    /***
     *return the array accesses count
     ***/
    public int getAccessCount() {
        //TO BE IMPLEMENTED
        return accessCount;
    }

    /***
     *reset the array access count to 0
     ***/
    public void resetAccessCount() {
        //TO BE IMPLEMENTED
        accessCount = 0;
    }

    private void resize(int capacity) {
        Item[] newItems = (Item[]) new Object[capacity];
        int newHeaderNext = capacity / 2 - 1;
        int newTailNext = newHeaderNext + 1;
        int currentHeadIndex = headNext + 1;
        int length = deque.length;
        for (int i = 0; i < size; i++) {
            int index = (currentHeadIndex + i) % length;
            newItems[newTailNext++] = deque[index];
            newTailNext = newTailNext % capacity;
        }
        this.headNext = newHeaderNext;
        this.tailNext = newTailNext;
        this.deque = newItems;

        accessCount += size;

    }

    public static void main(String[] args) {
        //TO BE IMPLEMENTED
        if (args.length < 2) {
            System.out.println("Usage: java Deque 100 10");
            return;
        }
        int N = Integer.parseInt(args[0]);
        int capacity = Integer.parseInt(args[1]);

        Deque<Integer> deque = new Deque<>(capacity);
        for (int i = 0; i < N; i++) {
            deque.addToBack(i);
        }
        int accessCountOne = deque.getAccessCount();
        deque.resetAccessCount();
        while (!deque.isEmpty()) {
            try {
                deque.getLast();
            } catch (EmptyDequeException e) {

            }
        }

        int accessCountTwo = deque.getAccessCount();

        System.out.println(" N = " + N + ", addToBack-AccessCount = " + accessCountOne + ", getLast-AccessCount = " + accessCountTwo);
    }
}
